// 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
// 输入: 10
// 输出: 36
// 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
// 思路，动态规划
// 1. `dp[i]`代表数字i，拆分后得到的最大乘积
// 2. 递推公式：有两种方式得到`dp[i]`,`j * (i - j)` 拆两个,或者`j * dp[i-j]`，拆两个以上，`dp[i] = Math.max(dp[i], j * (i - j), j * dp[i-j])`
// 3. dp初始化， 从2开始才有意义， `dp[2] = 1`
// 4. 遍历顺序： 从前往后，拆分一个数n使其乘积最大，一定是拆分成m个近似相同的子树，m大于等于2，所以只需要遍历到 `m / 2`
// 5. 举例
function integerBreak(n) {
    let dp = new Array(n + 1).fill(0)
    dp[2] = 1
    for (let i = 3; i <= n; i++) {
        for (let j = 1; j <= i / 2; j++) {
            dp[i] = Math.max(dp[i], j * (i - j), j * dp[i-j])
        }        
    }
    return dp[n]
}

console.log(integerBreak(10))